package org.example.leetCode;

/**
 * 134. 加油站
 * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
 * 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
 */
public class Code134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n=gas.length;
        int sum=0;
        int[] value=new int[n];
        for(int i=0;i<n;i++){
            value[i]=gas[i]-cost[i];
            sum=sum+value[i];
        }
        if(sum<0){
            return -1;
        }

        int start = 0;      // 起始位置
        int tank = 0;       // 油箱中的油量

        for (int i = 0; i < n; i++) {
            tank += value[i];   // 在第i个加油站加油并减去到下一个加油站的油耗

            // 如果油箱中的油量小于0，说明无法从start到达i+1
            if (tank < 0) {
                // 将起始位置设为i+1
                start = i + 1;
                // 重置油箱油量
                tank = 0;
            }
        }

        return start;
    }
}
